package qjc.i_图论;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class i2_糜烂的橘子 {
    /**
     * 解题思路：
     * 本题模拟腐烂橘子的扩散过程，求所有新鲜橘子变腐烂所需的最短时间（分钟）。
     * <p>
     * 核心思想：多源广度优先搜索（BFS）
     * <p>
     * 1. 初始时，将所有腐烂橘子（值为 2）加入队列，作为第 0 分钟的起点；
     * 2. 使用 BFS 按层遍历，每一层代表经过一分钟后的扩散结果；
     * 3. 每次从队列中取出当前所有腐烂橘子，尝试向四个方向（上下左右）感染相邻的新鲜橘子（值为 1）；
     * 4. 感染后，新鲜橘子变为腐烂（设为 2），计数减一，并加入队列供下一轮扩散；
     * 5. 每处理完一层（即当前队列中的所有橘子），时间 time 加 1；
     * 6. 当不再有新鲜橘子可感染（count == 0）或无法继续感染时停止；
     * 7. 若最后仍有新鲜橘子（count > 0），说明无法全部腐烂，返回 -1；否则返回总时间。
     * <p>
     * 关键点：
     * - 多个腐烂橘子同时开始扩散，因此初始将所有腐烂橘子入队；
     * - BFS 天然按“层”扩展，每层对应一分钟，保证时间最短；
     * - 使用 count 记录剩余新鲜橘子数量，控制循环终止；
     * - 用二维数组 dirs 表示四个方向，简化代码。
     * <p>
     * 时间复杂度 O(mn)，每个格子最多入队一次；
     * 空间复杂度 O(mn)，队列最大可能存储所有橘子。
     *
     * @param grid
     * @return
     */
    public int orangesRotting(int[][] grid) {
        int count = 0;
        int n = grid.length;
        int m = grid[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int time = 0;
        while (!queue.isEmpty() && count > 0) {
            int size = queue.size();
            time++;
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int x = cur[0];
                int y = cur[1];
                for (int[] dir : dirs) {
                    int newX = x + dir[0];
                    int newY = y + dir[1];
                    if (newX >= 0 && newX < n && newY >= 0 && newY < m && grid[newX][newY] == 1) {
                        grid[newX][newY] = 2;
                        queue.offer(new int[]{newX, newY});
                        count--;
                    }
                }
            }
        }
        return count > 0 ? -1 : time;
    }
}
